package java_0220.leetcode;

/**
 * 给定一棵二叉树，你需要计算它的直径长度。
 * 一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 */
public class Num543_MaxRoad {
    //存储当前二叉树的最长路径
    private int max=0;
    public int diameterOfBinaryTree(TreeNode root) {
        //边界
        if(root==null||(root.left==null&&root.right==null)){
            //空树或者只有根节点，不可能存在边
            return 0;
        }
        height(root);
        return max;
    }
    //递归求每个节点的高度
    //求高度的过程中顺带把最长路径给求了
    private int height(TreeNode root){
        if(root==null){
            return 0;
        }
        int l=height(root.left);
        int r=height(root.right);
        max=Math.max(max,l+r);
        //返回值是求树的深度
        return 1+Math.max(l,r);
    }
}
